1. Field of the Invention
The invention relates to the field of communication. More specifically, the invention relates to communication networks.
2. Background of the Invention
The multi-protocol label switching (MPLS) protocol may be categorized as a network layer protocol of the Open Standards Institute (OSI) reference model. MPLS provides a method for generically tunneling data through networks with label switched paths (LSPs). Traffic travels along an LSP with label stacks.
FIG. 1 (Prior Art) is a diagram of a label stack entry according to multi-protocol label switching (MPLS). A label stack entry 100 is a 32-bit value that includes the following fields: a label identifier field 101, a stack bit field 103, an experimental field 105, and a time to live field (TTL) 107. The label identifier field 101 includes a 20-bit label identifier for a label switched path (LSP). The stack bit field 103 includes a single bit to indicate whether the label stack entry 100 is the last label stack entry of a packet. The experimental field 105 includes 3 bits reserved for experimental purposes. The time to live field 107 includes 8 bits to indicate the number of hops a label stack entry should exist.
When a network device acting as a transit label switch router receives a packet with a label stack entry, the network device determines forwarding information for the packet by looking up the label identifier of the label stack entry in a label forwarding information base (LFIB). Some network devices search for an entry in the LFIB that matches the label identifier. Other network devices structure the LFIB as a hierarchy of indices. These network devices initially search for an index matching a certain number of the least significant bits of the label identifier. At each level of the hierarchy of indices, the network device progresses through the bits of the label identifier to the most significant bit. For example, a network device searches its LFIB for an index matching bits 0-11 of the label identifier. After finding a matching entry, the network device then searches for an entry matching bits 12–19 of the label identifier.
Both methods of organizing an LFIB lead to inefficient look-up of forwarding information for label switched packets.